import numpy as np
import time

def bitonic_sort(arr):
    n = len(arr)
    if n == 1:
        return arr

    # 分割数组为两部分
    mid = n // 2
    left = arr[:mid]
    right = arr[mid:]

    # 递归排序两部分
    left_sorted = bitonic_sort(left)
    right_sorted = bitonic_sort(right)

    # 合并排序后的两部分
    return merge_sorted(left_sorted, right_sorted)

def merge_sorted(left, right):
    i = j = 0
    sorted_array = []

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            sorted_array.append(left[i])
            i += 1
        else:
            sorted_array.append(right[j])
            j += 1

    # 添加剩余的元素
    while i < len(left):
        sorted_array.append(left[i])
        i += 1

    while j < len(right):
        sorted_array.append(right[j])
        j += 1

    return sorted_array



# 示例
arr = np.random.randint(0, 1000000, 1000000)

# 记录开始时间
start_time = time.time()
# 调用函数

sorted_arr = bitonic_sort(arr)
#print(sorted_arr)

# 记录结束时间
end_time = time.time()

# 计算并打印运行时间
print(f"函数运行时间为：{end_time - start_time} 秒")